package niuke;

/**
 * description:
 * author:zt
 * date:2021-09-10
 */

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
 * [要求]
 * 1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
 * 2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
 *
 * 每行有一个整数opt表示操作类型
 * 若opt=1，则接下来有一个整数N表示将N加入到结构中。
 * 若opt=2，则表示询问当前所有数的中位数
 */
public class NC131 {
    public double[] flowmedian (int[][] operations) {
        // write code here
        PriorityQueue<Integer> p1 = new PriorityQueue<>((a,b)->b-a);
        PriorityQueue<Integer> p2 = new PriorityQueue<>((a,b)->a-b);
        ArrayList<Double> res = new ArrayList<>();
        for (int i = 0; i < operations.length; i++) {
            if (operations[i][0]==1){
                int s1=p1.size(), s2=p2.size();
                if (s1==s2){
                    if (p2.isEmpty() || operations[i][1]<=p2.peek())
                        p1.add(operations[i][1]);
                    else {
                        p1.add(p2.poll());
                        p2.add(operations[i][1]);
                    }
                }
                else {
                    if (p1.peek()<=operations[i][1]) p2.add(operations[i][1]);
                    else {
                        p2.add(p1.poll());
                        p1.add(operations[i][1]);
                    }
                }
            }
            else if (operations[i][0]==2){
                if (p1.size()==p2.size()) res.add((p1.peek()+p2.peek())/2.0);
                else res.add((double)p1.peek());
            }
        }
        double[] r = new double[res.size()];
        for (int i = 0; i < res.size(); i++) {
            r[i] = res.get(i);
        }
        return r;
    }
}
